The invention relates the field of fitting mathematical expressions to data.
There are many known techniques for fitting both continuous functions and piecewise-linear expressions to data. These techniques have become more important recently since with current computing power it is now possible to rapidly solve mathematical expressions that were not solvable a few decades ago. Moreover, as the cost of computing power decreases new opportunities arise for solving problems in unexplored fields.
Where a few variables and tens or hundreds of data points are involved, techniques using heuristic approaches and intuition may be adequate. It is known, for instance, to use a piecewise-linear fitting representing the characteristics of transistors where the maximum value of all of the piecewise planes approximate the data. The breakpoint of the planes are selected heuristically since the operation of transistors are relatively simple and well understood. On the other hand, a complex problem such as airline scheduling may involve hundreds of thousands of variables with no intuitive guidelines to set initial bounds. There are countless other systems having thousands of variables which defy an intuitive approach. Thus there is a continuing need for rigorous methods that allow for the developing of expressions especially for complex systems.
Additionally, mathematical expressions that can be expressed as, or converted to, posynomial expressions lend themselves to geometric programs. These programs can be solved with efficient interior-point methods. This technique is known particularly for solving electrical circuit problems. See xe2x80x9cCMOS Operational Amplifier Design In Optimization Via Geometric Programming,xe2x80x9d by Hershenson, Boyd and Lee, Proceedings of the First International Workshop on Design of Mixed Mode Integrated Circuits and Applications, July 97 and xe2x80x9cAutomated Design of Folded-Cascode Op Amps with Sensitivity Analysis,xe2x80x9d by Herschenson, Boyd and Lee, 5th IEEE International Conference on Electronics, Circuits and System, September 98.
A computer implemented method for providing a mathematical representation of a system having a plurality of variables is disclosed. Planes are fitted to the data where each plane deviates from the data by no more than a predetermined tolerance in one sense. A plane is selected for inclusion in a set of planes if inclusion reduces the error between the set of planes and the data. After a plane is added to the set, refitting occurs and another plane is selected for inclusion in the set. This continues until there is no reduction in error from adding planes to the set. The maximum value of the planes in the set forms an expression which represents the data.
In an alternate embodiment a look ahead method is used which determines whether the inclusion of a particular plane in the set provides for more error reduction when taking into account the inclusion of planes in subsequent iterations.
In addition methods are described for providing a max-monomial approximation as well as a posynomial approximation.